package _08_DFS;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/permutations/
 * @Author: haogege
 * @Date: 2021/8/31
 */
public class _46_全排列1 {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length == 1) {
            List<Integer> result = new ArrayList<>();
            result.add(nums[0]);
            list.add(result);
            return list;
        }

        // 选中的全排列元素
        int[] check = new int[nums.length];
        // 已经选过的元素
        boolean[] isCheck = new boolean[nums.length];

        dfs(0, nums, check, isCheck, list);
        return list;
    }

    private void dfs(int i, int[] nums, int[] check, boolean[] isCheck, List<List<Integer>> list) {
        if (i == nums.length) {
            List<Integer> result = new ArrayList<>();
            for (int k : check) {
                result.add(k);
            }
            list.add(result);
            return;
        }

        // 遍历所有结果
        for (int j = 0; j < nums.length; j++) {
            // 排除遍历结果
            if (!isCheck[j]) {
                isCheck[j] = true;
                check[i] = nums[j];
                dfs(i + 1, nums, check, isCheck, list);
                isCheck[j] = false;
            }
        }
    }

}
